package com.剑指offer.第四章;

public class 链表中的数字相加 {

    /**
     * 先将两个链表进行反转
     * 然后从低位相加 之后再反转链表
     *
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode resolve(ListNode head1, ListNode head2) {
        ListNode rehead1 = convert(head1);
        ListNode rehead2 = convert(head2);
        return convert(addNum(rehead1, rehead2));
    }

    public static ListNode addNum(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode node = dummy;
        int carry = 0;
        while (head1 != null || head2 != null) {
            int sum = head1.val + head2.val + carry;
            carry = sum >= 10 ? 1 : 0;
            sum = carry > 0 ? sum - 10 : sum;
            ListNode node1 = new ListNode(sum);
            node.next = node1;
            node = node1;
            head1 = head1 == null ? null : head1.next;
            head2 = head2 == null ? null : head2.next;
        }
        if (carry > 0) {
            ListNode node1 = new ListNode(carry);
            node.next = node1;
        }
        return dummy.next;
    }

    public static ListNode convert(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            // 先将下一个节点保存下来，防止链表断开找不到
            ListNode next = cur.next;
            // 指向前一个节点
            cur.next = pre;
            // 记录当前节点 用于下个节点指向它
            pre = cur;
            cur = next;

        }
        return pre;
    }

    public static void main(String[] args) {

    }

}
